CS154 Spring 2003Practice Midterm 2

The practice midterm is below. Here are some facts about the actual midterm: (a) The midterm will be in class . (b) It is closed book, closed notes. Nothing will be permitted on your desk except your pen (pencil) and test. (c) You should bring photo ID. (d) There will be more than one version of the test. Each version will be of comparable difficulty. (e) If your cell-phone or beeper goes off you will be excused from the test at that point and graded on what you have done till your excusal. (f) One problem (less typos) on the actual test will be from the practice test.

1. Give a context free grammar for the following language:
{ wa^|w| | wÎ {a, b}^* }

2. Use the algorithm from class to convert the grammar you got in (1) into a PDA that recognizes the same language.

3. Give a PDA that accepts the language:
{ a^xb^yc^x+y | x,y natural numbers }

4. Use the algorithm from class to convert the PDA from (3) into a CFG that produces the same language.

5. Prove or give a counterexample: if L and L' are CFLs then L/L' is a context-free language.

6. Prove or give a counterexample: if L and L' are CFLs then LLL' is context-free.

7. Consider the CFG rule A-->BCDEF. Show how to convert this rule into an equivalent set of rules in Chomsky normal form.

8. Consider the CFG ( { o, c, S}, {S}, {S-->SS, S-->o S c; S-->e}, S}. Show how the dynamic program algorithm from class would determine if ocoococc is in this language.

9. Give the diagram of a TM that decides the language:
{ www | w Î {a, b}^* }

10. Show the sequence of configurations that your machine from (9) would go through to check if ababab was in (9)'s language.